package com.datastructure.test.uniquepathswithobstacles;

import java.util.ArrayList;

public class UniquePathsWithObstacles {

    public static void main(String[] args) {

    }
    public int nums;
    public boolean[][] flags;
    public int uniquePathsWithObstacles (ArrayList<ArrayList<Integer>> obstacleGrid) {
        // write code here
        int rows = obstacleGrid.size();
        int columns = obstacleGrid.get(0).size();
        int[][] dataArray = new int[rows][columns];
        flags = new boolean[rows][columns];
        ArrayList<Integer> obstacle;
        for (int i = 0; i < rows; i++) {
            obstacle = obstacleGrid.get(i);
            for (int j = 0; j < columns; j++) {
                dataArray[i][j]=obstacle.get(j);
            }
        }
        dfs(dataArray,rows-1,columns-1);
        return nums;
    }

    public void dfs(int[][] dataArray, int n, int m){
        if(n<0||m<0||n>=dataArray.length||m>=dataArray[0].length)return;
        if(flags[n][m])return;
        if(dataArray[n][m]==0)return;
        if(n==0&&m==0){
            nums++;
        }
        flags[n][m]=true;
        dfs(dataArray,n-1,m);
        dfs(dataArray,n,m-1);
        flags[n][m]=false;
    }

    public int uniquePathsWithObstacles1 (ArrayList<ArrayList<Integer>> obstacleGrid) {
        // write code here
        int m = obstacleGrid.size();
        int n = obstacleGrid.get(0).size();

        int[] dp = new int[n];
        for(int i=0;i<n;i++){
            if(obstacleGrid.get(0).get(i)==1) dp[i] = 1;
            else break;
        }

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                ArrayList<Integer> item = obstacleGrid.get(i);
                if(item.get(j)==1) dp[j] = dp[j-1] + dp[j];
                else dp[j] = 0;
            }
        }
        return dp[n-1];
    }

    public int uniquePathsWithObstacles2 (ArrayList<ArrayList<Integer>> obstacleGrid) {
        // write code here
        int m = obstacleGrid.size();
        int n = obstacleGrid.get(0).size();
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            if (obstacleGrid.get(i).get(0) == 0) {
                break;
            }
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            if (obstacleGrid.get(0).get(i) == 0) {
                break;
            }
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid.get(i).get(j) == 0) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}
